package dungeonTools;

import java.util.HashMap;

import dungeon.CompositeDungeon;
import dungeon.Dungeon;
import dungeonElements.Square;

/**
 * A class of that implements a KDTree structure for managing the Child
 * Dungeons of a Composite Dungeon.
 * 
 * All operations should happen in average case complexity O(log n),
 * except for the getAllDungeonsInNodeSubTree, which runs linear,
 * and Clear which uses constant time.
 * 
 * No guarantee is made regarding the uniqueness of added dungeons.
 * 
 * A node has either 2 childNodes, a divisionCoordinate and a 
 * divisionDirection that separate those childNodes,
 * OR
 * An enclosed dungeon and a the coordinate of the ORIGIN of that dungeon
 * 
 * A node can not have both of the above at the same time;
 * The other values will be NULL
 * 
 * @author Tom Jacobs & Ewoud De Moor
 * @version 3.0
 */
public final class KDTree {
	/**
	 * Variable registering the Direction of the NORMAL on the plane that seperates the 2 childs of this node
	 */
	private Direction divisionDirection;
	
	/**
	 * The coordinate of the ORIGIN of this node inside the CompositDungeon
	 */
	private final Coordinate basisCoordinate;
	
	/**
	 * The coordinate of the UPPER-NORTH-EAST corner of this node inside the CompositDungeon
	 */
	private final Coordinate expansionCoordinate;
	
	/**
	 * The first child node of this node
	 */
	private KDTree firstChild;
	
	/**
	 * The other child node of this node
	 */
	private KDTree otherChild;
	
	/**
	 * A coordinate in the plane that separates the 2 children of this node
	 */
	private Coordinate divisionCoordinate;
	
	/**
	 * The Dungeon enclosed by this node
	 */
	private Dungeon<? extends Square> enclosedDungeon;
	
	/**
	 * The Coordinate of that enclosed dungeon
	 */
	private Coordinate enclosedDungeonBasisCoordinate;
	
	/**
	 * The parent node of this node
	 */
	private KDTree parentNode;
	
	/**
	 * Creates a node with the following basis and expansion coordinates
	 * 
	 * @param basisCoordinate
	 * 		The coordinate of the ORIGIN of this node inside the CompositDungeon
	 * @param expansionCoordinate
	 * 		The coordinate of the UPPER-NORTH-EAST corner of this node inside the CompositDungeon
	 * @throws IllegalArgumentException
	 * 		The coordinates must be initialized
	 */
	public KDTree(Coordinate basisCoordinate, Coordinate expansionCoordinate) throws IllegalArgumentException{
		if((basisCoordinate == null) || (expansionCoordinate == null))
			throw new IllegalArgumentException("Please initialize all coordinates");
		this.basisCoordinate = basisCoordinate;
		this.expansionCoordinate = expansionCoordinate;
	}
	
	/**
	 * Adds a dungeon to this node. It will be placed in an automatically balanced subnode.
	 * 
	 * @param dungeon
	 * 		The dungeon to add
	 * @param dungeonBasisCoordinate
	 * 		The ORIGIN coordinate of that dungeon relative to the enclosing CompositDungeon
	 * @throws IllegalArgumentException
	 * 		The dungeon must be addable to this node
	 */
	public void addDungeonToNode(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate) throws IllegalArgumentException{
		getSmallestNodeFittingDungeon(dungeon, dungeonBasisCoordinate).putDungeonInThisNode(dungeon, dungeonBasisCoordinate);
	}
	
	/**
	 * Returns the parent node of this node
	 * 
	 * @return
	 * 		The parent node
	 * @throws UnsupportedOperationException
	 * 		The node can't be the root node
	 */
	private KDTree getParentNode() throws UnsupportedOperationException{
		if(!hasParentNode())
			throw new UnsupportedOperationException("This node is the root node");
		return parentNode;
	}

	/**
	 * Sets the parent node of this node
	 * 
	 * @param parentNode
	 * 		The parent node
	 * @throws IllegalStateException
	 * 		The parent node must have this one as one of his childs
	 */
	private void setParentNode(KDTree parentNode) throws IllegalStateException{
		if((parentNode.getFirstChild() != this) && (parentNode.getOtherChild() != this))
			throw new IllegalStateException("The parent node doesn't match this one as child");
		this.parentNode = parentNode;
	}
	
	/**
	 * Returns whether or not this node has a parent node
	 * 
	 * @return whether or not this node has a parent node
	 */
	private boolean hasParentNode() {
		return parentNode != null;
	}

	/**
	 * Sets the enclosed dungeon of a node, in case it is childLess
	 * 
	 * @param dungeon
	 * 		The dungeon to be enclosed
	 * @param dungeonBasisCoordinate
	 * 		The ORIGIN coordinate of that dungeon relative to the enclosing CompositDungeon
	 * @throws IllegalStateException
	 * 		The node can't already have an enclosed dungeon, and can't have any children.
	 */
	private void setEnclosedDungeon(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate) throws IllegalStateException{
		if(hasEnclosedDungeon())
			throw new IllegalStateException("This node already has an enclosed dungeon");
		if(hasChildren())
			throw new IllegalStateException("This node has children");
		enclosedDungeon = dungeon;
		enclosedDungeonBasisCoordinate = dungeonBasisCoordinate;
	}
	
	/**
	 * Sets new child nodes in this node
	 * 
	 * @param divisionCoordinate
	 * 		A coordinate in the dividing plane between those childs
	 * @param divisionDirection
	 * 		The Direction normal on the plane between those childs
	 * @throws IllegalStateException
	 * 		This node can't have any children already, and can't have an enclosed Dungeon
	 */
	private void setChildNodes(Coordinate divisionCoordinate, Direction divisionDirection) throws IllegalStateException{
		if(hasEnclosedDungeon())
			throw new IllegalStateException("This node has an enclosed dungeon");
		if(hasChildren())
			throw new IllegalStateException("This node already has children");
		switch(divisionDirection){
		case WEST:
			firstChild = new KDTree(getBasisCoordinate(), 
					new Coordinate(divisionCoordinate.getxCoordinate()
							,getExpansionCoordinate().getyCoordinate()
							,getExpansionCoordinate().getzCoordinate()));
			otherChild = new KDTree(new Coordinate(divisionCoordinate.getxCoordinate()
							,getBasisCoordinate().getyCoordinate()
							,getBasisCoordinate().getzCoordinate()),
							getExpansionCoordinate());
			break;
		case SOUTH:
			firstChild = new KDTree(getBasisCoordinate(), 
					new Coordinate(getExpansionCoordinate().getxCoordinate()
							,divisionCoordinate.getyCoordinate()
							,getExpansionCoordinate().getzCoordinate()));
			otherChild = new KDTree(new Coordinate(getBasisCoordinate().getxCoordinate()
							,divisionCoordinate.getyCoordinate()
							,getBasisCoordinate().getzCoordinate()),
							getExpansionCoordinate());
			break;
		case FLOOR:
			firstChild = new KDTree(getBasisCoordinate(), 
					new Coordinate(getExpansionCoordinate().getxCoordinate()
							,getExpansionCoordinate().getyCoordinate()
							,divisionCoordinate.getzCoordinate()));
			otherChild = new KDTree(new Coordinate(getBasisCoordinate().getxCoordinate()
							,getBasisCoordinate().getyCoordinate()
							,divisionCoordinate.getzCoordinate()),
							getExpansionCoordinate());
			break;
		default:
			throw new IllegalArgumentException("No valid divisionDirection.");
		}
		this.divisionCoordinate = divisionCoordinate;
		this.divisionDirection = divisionDirection;
		getFirstChild().setParentNode(this);
		getOtherChild().setParentNode(this);
		
	}
	
	/**
	 * Puts the dungeon inside this specific node
	 * 
	 * @param dungeon
	 * 		The dungeon to put
	 * @param dungeonBasisCoordinate
	 * 		The ORIGIN coordinate of that dungeon relative to the enclosing CompositDungeon
	 * @throws IllegalArgumentException
	 * 		The parameters must be initialized
	 * 		The dungeon must be allowed to be in this dungeon
	 * @throws IllegalStateException
	 * 		If a problem occurs on the way
	 */
	private void putDungeonInThisNode(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate) throws IllegalArgumentException,IllegalStateException{
		if((dungeon == null) || (dungeonBasisCoordinate == null))
			throw new IllegalArgumentException("Please initialize the parameters");
		if(!canAddDungeonToNode(dungeon, dungeonBasisCoordinate))
			throw new IllegalArgumentException("Dungeon can't be added to this node.");
		if(!hasChildren()){
			if(hasEnclosedDungeon()){
				Direction divisionDirection = calculateDivisionDirection(dungeon, dungeonBasisCoordinate);
				Dungeon<? extends Square> previousDungeon = getEnclosedDungeon();
				Coordinate previousDungeonBasisCoordinate = getEnclosedDungeonBasisCoordinate();
				enclosedDungeon = null;
				enclosedDungeonBasisCoordinate = null;
				if(getDungeonExpansionCoordinate(previousDungeon, previousDungeonBasisCoordinate)
						.isLowerThan(dungeonBasisCoordinate, divisionDirection)){
					setChildNodes(dungeonBasisCoordinate,divisionDirection);
					getFirstChild().putDungeonInThisNode(previousDungeon, previousDungeonBasisCoordinate);
					getOtherChild().putDungeonInThisNode(dungeon, dungeonBasisCoordinate);
				}
				else{
					setChildNodes(previousDungeonBasisCoordinate, divisionDirection);
					getFirstChild().putDungeonInThisNode(dungeon, dungeonBasisCoordinate);
					getOtherChild().putDungeonInThisNode(previousDungeon, previousDungeonBasisCoordinate);
				}
				return;
			}
			setEnclosedDungeon(dungeon, dungeonBasisCoordinate);
			return;
		}
		if(getFirstChild().fitsWithinThisNode(dungeonBasisCoordinate, getDungeonExpansionCoordinate(dungeon, dungeonBasisCoordinate)))
			getFirstChild().putDungeonInThisNode(dungeon, dungeonBasisCoordinate);
		else if(getOtherChild().fitsWithinThisNode(dungeonBasisCoordinate, getDungeonExpansionCoordinate(dungeon, dungeonBasisCoordinate)))
			getOtherChild().putDungeonInThisNode(dungeon, dungeonBasisCoordinate);
		else{
			refactorThisNode(dungeon, dungeonBasisCoordinate);
		}
			
	}

	/**
	 * Refactors all subnodes of this node to add the dungeon inside it
	 * 
	 * @param dungeon
	 * 		The dungeon to add
	 * @param dungeonBasisCoordinate
	 * 		The ORIGIN coordinate of that dungeon relative to the enclosing CompositDungeon
	 * @throws IllegalStateException
	 * 		The node must have children
	 * 		The node can't have an enclosed dungeon
	 * @throws IllegalArgumentException
	 * 		The parameters must be initialized
	 */
	private void refactorThisNode(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate) throws IllegalArgumentException, IllegalStateException{
		if((dungeon == null) || (dungeonBasisCoordinate == null))
			throw new IllegalArgumentException("Please initialize the parameters");
		if(!hasChildren())
			throw new IllegalStateException("This node doesn't have any children");
		if(hasEnclosedDungeon())
			throw new IllegalStateException("This node has an enclosed dungeon");
		HashMap<Dungeon<? extends Square>,Coordinate> allSubDungeons = getAllDungeonsInNodeSubTree();
		allSubDungeons.put(dungeon, dungeonBasisCoordinate);
		firstChild = null;
		otherChild = null;
		divisionCoordinate = null;
		divisionDirection = null;
		refactorThisNode(allSubDungeons);
	}

	/**
	 * Refactors all subnodes of this node to add the dungeons inside it
	 * 
	 * @param allSubDungeons
	 * 		A map of all dungeons and their coordinates to be put inside this nodes subTree
	 * @throws IllegalStateException
	 * 		The node must have children
	 * 		The node can't have an enclosed dungeon
	 * @throws IllegalArgumentException
	 * 		The parameters must be initialized
	 */
	private void refactorThisNode(HashMap<Dungeon<? extends Square>, Coordinate> allSubDungeons) throws IllegalStateException, IllegalArgumentException{
		if((allSubDungeons == null) || (allSubDungeons.size() == 0))
			throw new IllegalArgumentException("Please initialize and fill the HashMap");
		if(hasChildren())
			throw new IllegalStateException("This node has children");
		if(hasEnclosedDungeon())
			throw new IllegalStateException("This node has an enclosed dungeon");
		if(allSubDungeons.size() == 1){
			for(Dungeon<? extends Square> dungeon : allSubDungeons.keySet()){
				setEnclosedDungeon(dungeon, allSubDungeons.get(dungeon));
				return;
			}
		}
		HashMap<Dungeon<? extends Square>,Coordinate> firstChildMap = new HashMap<Dungeon<? extends Square>,Coordinate>();
		HashMap<Dungeon<? extends Square>,Coordinate> otherChildMap = new HashMap<Dungeon<? extends Square>,Coordinate>();
		Direction[] divisionDirections = {Direction.WEST,Direction.SOUTH,Direction.FLOOR};
		Direction divisionDirection = null;
		Coordinate divisionCoordinate = null;
		CoordinateLoop:
			for(Coordinate dungeonBasisCoordinate : allSubDungeons.values()){	
				for(Direction direction : divisionDirections){
					for(Dungeon<? extends Square> comparisonDungeon : allSubDungeons.keySet()){
						Coordinate comparisonDungeonBasisCoordinate = allSubDungeons.get(comparisonDungeon);
						if(getDungeonExpansionCoordinate(comparisonDungeon, comparisonDungeonBasisCoordinate)
								.isLowerThan(dungeonBasisCoordinate, direction))
							firstChildMap.put(comparisonDungeon,comparisonDungeonBasisCoordinate);
						else if(!comparisonDungeonBasisCoordinate.isLowerThan(dungeonBasisCoordinate, direction))
							otherChildMap.put(comparisonDungeon, comparisonDungeonBasisCoordinate);
						else{
							firstChildMap.clear();
							otherChildMap.clear();
							break;
						}
						divisionDirection = direction;
						divisionCoordinate = dungeonBasisCoordinate;
						if((firstChildMap.size() + otherChildMap.size() == allSubDungeons.size()) 
								&& (firstChildMap.size() != 0) && (otherChildMap.size() != 0))
							break CoordinateLoop;

					}
				}
				if(!((firstChildMap.size() + otherChildMap.size() == allSubDungeons.size()) 
						&& (firstChildMap.size() != 0) && (otherChildMap.size() != 0))){
					firstChildMap.clear();
					otherChildMap.clear();
				}
	}
	assert !((divisionCoordinate == null) || (divisionDirection == null) 
			|| (firstChildMap.size() == 0) || (otherChildMap.size() == 0));
	setChildNodes(divisionCoordinate, divisionDirection);
	getFirstChild().refactorThisNode(firstChildMap);
	getOtherChild().refactorThisNode(otherChildMap);
}

/**
 * Gets a Map of all dungeons in this nodes' subTree,
 * mapped onto the coordinates of their origins
 * 
 * @return
 * 			That map
 */
public HashMap<Dungeon<? extends Square>,Coordinate> getAllDungeonsInNodeSubTree() {
	HashMap<Dungeon<? extends Square>, Coordinate> allSubDungeons = new HashMap<Dungeon<? extends Square>,Coordinate>();
	if(hasEnclosedDungeon()){
		allSubDungeons.put(getEnclosedDungeon(), getEnclosedDungeonBasisCoordinate());
	}
	else if(hasChildren()){
		allSubDungeons.putAll(getFirstChild().getAllDungeonsInNodeSubTree());
		allSubDungeons.putAll(getOtherChild().getAllDungeonsInNodeSubTree());
	}
		return allSubDungeons;
	}
	
	/**
	 * Removes a specific dungeon at those coordinates from the subTree of this node
	 * 
	 * @param dungeon
	 * 		The dungeon to remove
	 * @param dungeonBasisCoordinate
	 * 		The coordinates that dungeon is located at
	 * @throws IllegalArgumentException
	 * 		The dungeon must be placed inside this nodes' subTree at those coordinates
	 */
	public void removeDungeonFromSubNode(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate) throws IllegalArgumentException{
		KDTree nodeEnclosingDungeon = getSmallestNodeFittingDungeon(dungeon, dungeonBasisCoordinate);
		if((nodeEnclosingDungeon.getEnclosedDungeon() != dungeon) 
				|| (!nodeEnclosingDungeon.getEnclosedDungeonBasisCoordinate().equals(dungeonBasisCoordinate)))
				throw new IllegalArgumentException("Dungeon not at this node at that coordinate");
		KDTree parentNode = nodeEnclosingDungeon.getParentNode();
		if(parentNode.getFirstChild() == nodeEnclosingDungeon){
			parentNode.enclosedDungeon = parentNode.getOtherChild().getEnclosedDungeon();
			parentNode.enclosedDungeonBasisCoordinate = parentNode.getOtherChild().getEnclosedDungeonBasisCoordinate();
		}
		else{
			parentNode.enclosedDungeon = parentNode.getFirstChild().getEnclosedDungeon();
			parentNode.enclosedDungeonBasisCoordinate = parentNode.getFirstChild().getEnclosedDungeonBasisCoordinate();
		}
		parentNode.divisionCoordinate = null;
		parentNode.divisionDirection = null;
		parentNode.firstChild = null;
		parentNode.otherChild = null;
	}

	/**
	 * Calculates the new division direction of this node so that it's current
	 * enclosed dungeon and the new dungeon to add fall in 2 non-overlapping childs
	 * 
	 * @param newDungeonToAdd
	 * 		The new dungeon to be added
	 * @param newDungeonToAddBasisCoordinate
	 * 		The coordinate of that new dungeon's ORIGIN
	 * @return
	 * 		The Direction in which no overlap occurs
	 * @throws IllegalArgumentException
	 * 		The parameters must be initialized
	 * 		This node must have an enclosed dungeon
	 * @throws IllegalStateException
	 * 		A valid direction must exist
	 */
	private Direction calculateDivisionDirection(Dungeon<? extends Square> newDungeonToAdd, Coordinate newDungeonToAddBasisCoordinate) throws IllegalArgumentException, IllegalStateException{
		if((newDungeonToAdd == null) || (newDungeonToAddBasisCoordinate == null))
			throw new IllegalArgumentException("Please intialize all parameters");
		if(!hasEnclosedDungeon())
			throw new IllegalStateException("This node doesn't have an enclosed dungeon");
		Coordinate newDungeonExpansionCoordinate = getDungeonExpansionCoordinate(newDungeonToAdd, newDungeonToAddBasisCoordinate);
		Coordinate enclosedDungeonExpansionCoordinate = getDungeonExpansionCoordinate(getEnclosedDungeon(), getEnclosedDungeonBasisCoordinate());
		if(newDungeonExpansionCoordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.SOUTH)
				|| enclosedDungeonExpansionCoordinate.isLowerThan(newDungeonToAddBasisCoordinate, Direction.SOUTH))
			return Direction.SOUTH;
		if(newDungeonExpansionCoordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.WEST)
				|| enclosedDungeonExpansionCoordinate.isLowerThan(newDungeonToAddBasisCoordinate, Direction.WEST))
			return Direction.WEST;
		if(newDungeonExpansionCoordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.FLOOR)
				|| enclosedDungeonExpansionCoordinate.isLowerThan(newDungeonToAddBasisCoordinate, Direction.FLOOR))
			return Direction.FLOOR;
		throw new IllegalStateException("No valid direction exists??");
	}

	/**
	 * Gets the division direction of this node
	 * 
	 * @return the division direction of this node
	 */
	private Direction getDivisionDirection() {
		return divisionDirection;
	}

	/**
	 * Gets a coordinate in the division plane of this node
	 * 
	 * @return a coordinate in the division plane of this node
	 */
	private Coordinate getDivisionCoordinate() {
		return divisionCoordinate;
	}

	/**
	 * Gets the coordinate of the ORIGIN of the enclosed dungeon,
	 * relative to the enclosing CompositDungeon
	 * 
	 * @return That coordinate
	 */
	private Coordinate getEnclosedDungeonBasisCoordinate() {
		return enclosedDungeonBasisCoordinate;
	}

	/**
	 * Gets the coordinate of the ORIGIN of this node,
	 * relative to the enclosing CompositDungeon
	 * 
	 * @return that coordinate
	 */
	private Coordinate getBasisCoordinate(){
		return basisCoordinate;
	}
	
	/**
	 * Gets the coordinate of the UPPER-NORTH-EAST corner of this node,
	 * relative to the enclosing CompositDungeon
	 * 
	 * @return that coordinate
	 */
	private Coordinate getExpansionCoordinate(){
		return expansionCoordinate;
	}

	/**
	 * Gets the first of the child nodes of this node
	 * 
	 * @return the first child node
	 */
	private KDTree getFirstChild() {
		return firstChild;
	}

	/**
	 * Gets the second of the child nodes of this node
	 * 
	 * @return the other child node
	 */
	private KDTree getOtherChild() {
		return otherChild;
	}
	
	/**
	 * Gets the dungeon enclosed in this node
	 * 
	 * @return the enclosed dungeon
	 */
	private Dungeon<? extends Square> getEnclosedDungeon(){
		return enclosedDungeon;
	}
	
	/**
	 * Return whether or not a dungeon with those ORIGIN (basis) and 
	 * UPPER-NORTH-EAST (expansion) coordinates fits within this node
	 * 
	 * @param dungeonBasisCoordinate
	 * 		The dungeons ORIGIN coordinate
	 * @param dungeonExpansionCoordinate
	 * 		The dungeons expansion coordinate
	 * @return
	 * 		Whether or not that dungeon will fit in this node
	 */
	private boolean fitsWithinThisNode(Coordinate dungeonBasisCoordinate, Coordinate dungeonExpansionCoordinate) {
		if((dungeonBasisCoordinate.isLowerThan(getBasisCoordinate(),Direction.FLOOR))
				|| (dungeonBasisCoordinate.isLowerThan(getBasisCoordinate(),Direction.SOUTH))
				|| (dungeonBasisCoordinate.isLowerThan(getBasisCoordinate(),Direction.WEST)))
			return false;
		if((getExpansionCoordinate().isLowerThan(dungeonExpansionCoordinate, Direction.FLOOR))
				|| (getExpansionCoordinate().isLowerThan(dungeonExpansionCoordinate, Direction.SOUTH))
				|| (getExpansionCoordinate().isLowerThan(dungeonExpansionCoordinate, Direction.WEST)))
			return false;
		return true;
	}

	/**
	 * Returns whether or not this node has an enclosed dungeon
	 * 
	 * @return whether or not this node has an enclosed dungeon
	 */
	private boolean hasEnclosedDungeon() {
		return getEnclosedDungeon() != null;
	}
	
	/**
	 * Gets the smallest node where a specific dungeon would FIT INSIDE at those
	 * basis coordinates. No guarantee is made towards overlap, childNodes or the
	 * enclosed dungeon of that specific node that will be returned, only that it's
	 * the smallest node that can spatially fit around the dungeon.
	 * 
	 * @param dungeon
	 * 		The dungeon for which to get the node
	 * @param dungeonBasisCoordinate
	 * 		The coordinate of that dungeons ORIGIN
	 * @return
	 * 		The smallest node that could enclose that dungeon
	 * @throws IllegalArgumentException
	 * 		The arguments must be initialized
	 * 		The dungeon must at least fit inside this node
	 */
	private KDTree getSmallestNodeFittingDungeon(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate) throws IllegalArgumentException{
		if((dungeon == null) || (dungeonBasisCoordinate == null))
			throw new IllegalArgumentException("Please initialize the parameters");
		if(!fitsWithinThisNode(dungeonBasisCoordinate, getDungeonExpansionCoordinate(dungeon, dungeonBasisCoordinate)))
			throw new IllegalArgumentException("Dungeon doesn't even fit inside this node");
		if(hasChildren()){
			if(getDungeonExpansionCoordinate(dungeon, dungeonBasisCoordinate).isLowerThan(getDivisionCoordinate(), getDivisionDirection()))
				return getFirstChild().getSmallestNodeFittingDungeon(dungeon, dungeonBasisCoordinate);
			if(!dungeonBasisCoordinate.isLowerThan(getDivisionCoordinate(), getDivisionDirection()))
				return getOtherChild().getSmallestNodeFittingDungeon(dungeon, dungeonBasisCoordinate);
		}
		return this;
	}
	
	/**
	 * Returns whether or not the dungeon can be added to this node
	 * 
	 * @param dungeon
	 * 		The dungeon to be added
	 * @param dungeonBasisCoordinate
	 * 		The coordinate of the ORIGIN of that dungeon, relative to the enclosing CompositDungeon
	 * @return
	 * 		Whether or not the dungeon can be added (without overlap and such)
	 * @throws IllegalArgumentException
	 * 		The parameters must be initialized
	 */
	public boolean canAddDungeonToNode(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate) throws IllegalArgumentException{
		if((dungeon == null) || (dungeonBasisCoordinate == null))
			throw new IllegalArgumentException("Please initialize all parameters");
		if(!fitsWithinThisNode(dungeonBasisCoordinate, getDungeonExpansionCoordinate(dungeon, dungeonBasisCoordinate)))
			return false;
		return !getSmallestNodeFittingDungeon(dungeon, dungeonBasisCoordinate)
			.hasSubTreeDungeonOverlapping(dungeon, dungeonBasisCoordinate);
	}
	
	/**
	 * Returns whether or not the dungeons in the subTree of this node overlap
	 * with spatially this dungeon should it be added to the subTree
	 * 
	 * @param dungeon
	 * 		The dungeon to check for
	 * @param dungeonBasisCoordinate
	 * 		The ORIGIN coordinate of that dungeon
	 * @return
	 * 		Whether or not adding this dungeon would create overlaps
	 * @throws IllegalArgumentException
	 * 		All parameters must be initialized
	 */
	private boolean hasSubTreeDungeonOverlapping(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate) throws IllegalArgumentException{
		if((dungeon == null) || (dungeonBasisCoordinate == null))
			throw new IllegalArgumentException("Please initialize the parameters");
		if(!hasChildren()){
			if(hasEnclosedDungeon())
				return hasOverlapWithEnclosedDungeon(dungeon, dungeonBasisCoordinate);
			return false;
		}
		return (getFirstChild().hasSubTreeDungeonOverlapping(dungeon, dungeonBasisCoordinate)) 
			|| (getOtherChild().hasSubTreeDungeonOverlapping(dungeon, dungeonBasisCoordinate));
	}

	/**
	 * Checks whether or not the dungeon in the parameter overlaps with the dungeon
	 * enclosed in this node
	 * 
	 * @param dungeon
	 * 		The dungeon to check for
	 * @param dungeonBasisCoordinate
	 * 		The ORIGIN coordinate of that dungeon
	 * @return
	 * 		Whether or not the dungeon overlaps with the enclosed dungeon in this node
	 * @throws IllegalArgumentException
	 * 		All parameters must be initialized
	 */
	private boolean hasOverlapWithEnclosedDungeon(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate) throws IllegalArgumentException{
		if((dungeon == null) || (dungeonBasisCoordinate == null))
			throw new IllegalArgumentException("Please initialize the parameters");
		if(!hasEnclosedDungeon())
			return false;
		Coordinate dungeonExpansionCoordinate = getDungeonExpansionCoordinate(dungeon, dungeonBasisCoordinate);
		Coordinate enclosedDungeonExpansionCoordinate = getDungeonExpansionCoordinate(getEnclosedDungeon(), getEnclosedDungeonBasisCoordinate());
		return !((dungeonExpansionCoordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.WEST))
			|| (dungeonExpansionCoordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.SOUTH))
			|| (dungeonExpansionCoordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.FLOOR))
			|| (enclosedDungeonExpansionCoordinate.isLowerThan(dungeonBasisCoordinate, Direction.WEST))
			|| (enclosedDungeonExpansionCoordinate.isLowerThan(dungeonBasisCoordinate, Direction.SOUTH))
			|| (enclosedDungeonExpansionCoordinate.isLowerThan(dungeonBasisCoordinate, Direction.FLOOR)));
		
	}

	/**
	 * Returns whether or not this node has children
	 * 
	 * @return whether or not this node has children
	 */
	private boolean hasChildren() {
		return (firstChild != null) || (otherChild != null);
	}
	
	/**
	 * Calculates the coordinate of the UPPER-NORTH-EAST corner of a dungeon
	 * 
	 * @param dungeon
	 * 		The dungeon for which to calculate
	 * @param dungeonBasisCoordinate
	 * 		The coordinate of that dungeons ORIGIN
	 * @return
	 * 		The coordinate of the UPPER-NORTH-EAST corner
	 */
	private Coordinate getDungeonExpansionCoordinate(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate){
		if((dungeon == null) || (dungeonBasisCoordinate == null))
			throw new IllegalArgumentException("Please initialize the parameters");
		return new Coordinate(dungeonBasisCoordinate.getxCoordinate() + dungeon.getXSize()-1,
				dungeonBasisCoordinate.getyCoordinate() + dungeon.getYSize()-1,
				dungeonBasisCoordinate.getzCoordinate() + dungeon.getZSize()-1);
	}
	
	/**
	 * Return whether or not this node has a dungeon enclosed in one
	 * of it's childNodes, that contains the specific coordinate
	 * 
	 * @param coordinate
	 * 		The coordinate to check for
	 * @return
	 * 		Whether or not there is such a dungeon
	 */
	public boolean hasChildDungeonContainingCoordinate(Coordinate coordinate){
		if(coordinate == null)
			throw new IllegalArgumentException("Please initialize all parameters");
		if(coordinate.isLowerThan(getBasisCoordinate(), Direction.SOUTH)
				|| coordinate.isLowerThan(getBasisCoordinate(), Direction.WEST)
				|| coordinate.isLowerThan(getBasisCoordinate(), Direction.FLOOR)
				|| getExpansionCoordinate().isLowerThan(coordinate, Direction.SOUTH)
				|| getExpansionCoordinate().isLowerThan(coordinate, Direction.FLOOR)
				|| getExpansionCoordinate().isLowerThan(coordinate, Direction.WEST))
			return false;
		if(!hasChildren()){
			if(!hasEnclosedDungeon())
				return false;
			Coordinate enclosedDungeonExpansionCoordinate = getDungeonExpansionCoordinate(getEnclosedDungeon(), getEnclosedDungeonBasisCoordinate());
			return !(coordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.SOUTH)
				|| coordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.WEST)
				|| coordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.FLOOR)
				|| enclosedDungeonExpansionCoordinate.isLowerThan(coordinate, Direction.SOUTH)
				|| enclosedDungeonExpansionCoordinate.isLowerThan(coordinate, Direction.FLOOR)
				|| enclosedDungeonExpansionCoordinate.isLowerThan(coordinate, Direction.WEST));
		}
		if(coordinate.isLowerThan(getDivisionCoordinate(), getDivisionDirection()))
			return getFirstChild().hasChildDungeonContainingCoordinate(coordinate);
		return getOtherChild().hasChildDungeonContainingCoordinate(coordinate);
	}

	/**
	 * Returns the Dungeon in one of the childNodes of this node that contains
	 * the coordinate, should such a dungeon exist
	 * 
	 * @param coordinate
	 * 		The coordinate for which to get the enclosing dungeon
	 * @return
	 * 		The dungeon containing that coordinate
	 * @throws IllegalArgumentException
	 * 		Such a dungeon must exist
	 */
	public Dungeon<? extends Square> getChildDungeonContainingCoordinate(Coordinate coordinate) throws IllegalArgumentException{
		if(coordinate.isLowerThan(getBasisCoordinate(), Direction.SOUTH)
				|| coordinate.isLowerThan(getBasisCoordinate(), Direction.WEST)
				|| coordinate.isLowerThan(getBasisCoordinate(), Direction.FLOOR)
				|| getExpansionCoordinate().isLowerThan(coordinate, Direction.SOUTH)
				|| getExpansionCoordinate().isLowerThan(coordinate, Direction.FLOOR)
				|| getExpansionCoordinate().isLowerThan(coordinate, Direction.WEST))
			throw new IllegalArgumentException("Coordinate not inside this node");
		if(!hasChildren()){
			if(!hasEnclosedDungeon())
				throw new IllegalArgumentException("This coordinate doesn't fall inside any childdungeons");
			Coordinate enclosedDungeonExpansionCoordinate = getDungeonExpansionCoordinate(getEnclosedDungeon(), getEnclosedDungeonBasisCoordinate());
			if(coordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.SOUTH)
				|| coordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.WEST)
				|| coordinate.isLowerThan(getEnclosedDungeonBasisCoordinate(), Direction.FLOOR)
				|| enclosedDungeonExpansionCoordinate.isLowerThan(coordinate, Direction.SOUTH)
				|| enclosedDungeonExpansionCoordinate.isLowerThan(coordinate, Direction.FLOOR)
				|| enclosedDungeonExpansionCoordinate.isLowerThan(coordinate, Direction.WEST))
				throw new IllegalArgumentException("This coordinate doesn't fall inside any childdungeons");
			return getEnclosedDungeon();
		}
		if(coordinate.isLowerThan(getDivisionCoordinate(), getDivisionDirection()))
			return getFirstChild().getChildDungeonContainingCoordinate(coordinate);
		return getOtherChild().getChildDungeonContainingCoordinate(coordinate);
	}
	
	/**
	 * Checks whether or not a dungeon is allowed to have a certain new size,
	 * and thus won't cause any overlaps.
	 * 
	 * No checking is done on potential shrinking of dungeons, as those
	 * will always return true, even though they aren't allowed.
	 * 
	 * @param dungeon
	 * 		The dungeon for which to check the new size
	 * @param dungeonBasisCoordinate
	 * 		The coordinate of that dungeons ORIGIN relative to its enclosing CompositDungeon
	 * @param newXSize
	 * 		The new X size of the dungeon
	 * @param newYSize
	 * 		The new Y size of the dungeon
	 * @param newZSize
	 * 		The new Z size of the dungeon
	 * @return
	 * 		Whether or not this dungeon is allowed to grow to it's new size
	 * @throws IllegalArgumentException
	 * 		The parameters must be initialized
	 * 		The dungeon must be in this nodes' subTree
	 */
	public boolean dungeonCanHaveNewSize(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate, long newXSize, long newYSize, long newZSize)
	throws IllegalArgumentException{
		if((dungeon == null) || (dungeonBasisCoordinate == null))
			throw new IllegalArgumentException("Please initialize all parameters");
		removeDungeonFromSubNode(dungeon, dungeonBasisCoordinate);
		if(canAddDungeonToNode(new CompositeDungeon<Square>(newXSize,newYSize,newZSize), dungeonBasisCoordinate)){
			addDungeonToNode(dungeon, dungeonBasisCoordinate);
			return true;
		}
		addDungeonToNode(dungeon, dungeonBasisCoordinate);
		return false;
	}
	
	/**
	 * Sets the new size of the dungeon int this nodes' subTree, to ensure internal consistency
	 * 
	 * This method should be called AFTER the dungeons new size has been set.
	 * 
	 * @param dungeon
	 * 		The dungeon whose size must be set
	 * @param dungeonBasisCoordinate
	 * 		The coordinate of that dungeons ORIGIN relative to its enclosing CompositDungeon
	 * @throws IllegalArgumentException
	 * 		The dungeon must be allowed to have that new size
	 */
	public void setNewDungeonSize(Dungeon<? extends Square> dungeon, Coordinate dungeonBasisCoordinate) throws IllegalArgumentException{
		if(!dungeonCanHaveNewSize(dungeon, dungeonBasisCoordinate, dungeon.getXSize(), dungeon.getYSize(),dungeon.getZSize())){
			throw new IllegalArgumentException("The dungeon can't have that new size");
		}
		removeDungeonFromSubNode(dungeon, dungeonBasisCoordinate);
		addDungeonToNode(dungeon, dungeonBasisCoordinate);
	}
	
	/**
	 * Clears this node and it's subTree. Equivalent with replacing this
	 * node with a newly created one of the same size.
	 */
	public void clear(){
		divisionCoordinate = null;
		firstChild = null;
		otherChild = null;
		divisionDirection = null;
		enclosedDungeon = null;
		enclosedDungeonBasisCoordinate = null;
	}
	
}
